package com.itheima.leetcode.od.b.logicalsimulation;

import java.util.Arrays;
import java.util.LinkedList;

/**
 * (C卷,200分)- 贪吃蛇（Java & JS & Python）
 * <p>
 * 题目描述
 * <p>
 * 贪吃蛇是一个经典游戏，蛇的身体由若干方格连接而成，身体随蛇头移动。蛇头触碰到食物时，蛇的长度会增加一格。蛇头和身体的任一方格或者游戏版图边界碰撞时，游戏结束。
 * <p>
 * 下面让我们来完成贪吃蛇游戏的模拟。
 * <p>
 * 给定一个N*M的数组arr，代表N*M个方格组成的版图，贪吃蛇每次移动一个方格。
 * <p>
 * 若arr[i][j] == ‘H’，表示该方格为贪吃蛇的起始位置；
 * <p>
 * 若arr[i][j] == ‘F’，表示该方格为食物，
 * <p>
 * 若arr[i][j] == ‘E’，表示该方格为空格。
 * <p>
 * 贪吃蛇初始长度为1，初始移动方向为向左。
 * <p>
 * 为给定一系列贪吃蛇的移动操作，返回操作后蛇的长度，如果在操作执行完之前已经游戏结束，返回游戏结束时蛇的长度。
 * <p>
 * 贪吃蛇移动、吃食物和碰撞处理的细节见下面图示：
 * <p>
 * <p>
 * <p>
 * 图1：截取了贪吃蛇移动的一个中间状态，H表示蛇头，F表示食物，数字为蛇身体各节的编号，蛇为向左移动，此时蛇头和食物已经相邻
 * <p>
 * 图2：蛇头向左移动一格，蛇头和食物重叠，注意此时食物的格子成为了新的蛇头，第1节身体移动到蛇头位置，第2节身体移动到第1节身体位置，以此类推，最后添加第4节身体到原来第3节身体的位置。
 * <p>
 * 图3：蛇头继续向左移动一格，身体的各节按上述规则移动，此时蛇头已经和边界相邻，但还未碰撞。
 * <p>
 * 图4：蛇头继续向左移动一格，此时蛇头已经超过边界，发生碰撞，游戏结束。
 * <p>
 * 图5和图6给出一个蛇头和身体碰撞的例子，蛇为向上移动。
 * <p>
 * 图5时蛇头和第7节身体相邻，但还未碰撞；
 * <p>
 * 图6蛇头向上移动一格，此时蛇头和第8节身体都移动到了原来第7节身体的位置，发生碰撞，游戏结束。
 * <p>
 * 输入描述
 * <p>
 * 输入第一行为空格分隔的字母，代表贪吃蛇的移动操作。
 * <p>
 * 字母取值为U、D、L、R和G，
 * <p>
 * U、D、L、R分别表示贪吃蛇往上、下、左、右和转向，转向时贪吃蛇不移动 ，G表示贪吃蛇按当前的方向移动一格。
 * <p>
 * 用例保证输入的操作正确。
 * <p>
 * 第二行为空格分隔的两个数，指定N和M，为数组的行和列数。
 * <p>
 * 余下N行每行是空格分隔的M个字母。字母取值为H、F和E，H表示贪吃蛇的起始位置，F表示食物，E表示该方格为空。
 * <p>
 * 用例保证有且只有一个H，而F和E会有多个。
 * <p>
 * 输出描述
 * <p>
 * 输出一个数字，为蛇的长度。
 * <p>
 * 用例
 * <p>
 * 输入	D G G
 * <p>
 * 3 3
 * <p>
 * F F F
 * <p>
 * F F H
 * <p>
 * E F E
 * <p>
 * 输出	1
 * 说明
 * 地图表示为：
 * <p>
 * 蛇头 H(Head)
 * <p>
 * 食物 F(Food)
 * <p>
 * E表示该方格为空
 * <p>
 * 四个方向分别表示为：
 * <p>
 * 向上 U(up)
 * 向下 D(down)
 * 向左 L(Left)
 * 向右 R(Right)
 * <p>
 * 题目解析
 * <p>
 * 纯逻辑题。
 * <p>
 * 本题难点在于当贪吃蛇移动后，更新贪吃蛇的位置，以及矩阵各坐标的信息的逻辑。
 * <p>
 * 首先，我使用一个数组snake来维护贪吃蛇的位置，蛇头就是snake[0]。
 * <p>
 * 当贪吃蛇移动时，如果蛇头去往的位置是空地，即matrix[i][j] = 'E'的话，则
 * <p>
 * snake.unshift([i,j])
 * <p>
 * let [aI, aJ] = snake.pop() // 由于去往的是空地，因此贪吃蛇不会生长，所以蛇尾的位置要pop出去
 * <p>
 * matrix[aI][aJ] = 'E' // 并且要更新pop出去的位置为空地
 * <p>
 * matrix[i][j] = 'H' // 而蛇头达到的新位置要更新为蛇头位置H
 * <p>
 * 当贪吃蛇移动时，如果蛇头去往的位置是食物，即matrix[i][j] = 'F'的话，则
 * <p>
 * snake.unshift([i,j])
 * <p>
 * matrix[i][j] = 'H' // 更新蛇头位置
 * <p>
 * 当贪吃蛇移动时，如果蛇头去往的位置是自己的身体，即matrix[i][j] = 'H'，
 * <p>
 * 注意我这里并不需要根据‘H’来判断移动中蛇头的位置，而是总是用snake[0]作为蛇头，因此matrix[i][j] = 'H'可以直接用于标记贪吃蛇身体，来区别F、E。
 * <p>
 * 则，此时游戏结束，输出snake.length
 * <p>
 * 另外，当贪吃蛇移动的位置越界了，游戏也结束，输出snake.length
 * <p>
 * 自测用例
 * <p>
 * <p>
 * <p>
 * D G L G G U G G R G G D G L G
 * <p>
 * 3 3
 * <p>
 * F F F
 * <p>
 * F F H
 * <p>
 * E F E
 * <p>
 * 最终贪吃蛇的长度为7
 * <p>
 * <p>
 * <p>
 * D G L G U G R G U G L G D G
 * <p>
 * 3 3
 * <p>
 * F F F
 * <p>
 * F F H
 * <p>
 * E F E
 * <p>
 * 最终贪吃蛇的长度为5
 */
public class Snake {
    public static void main(String[] args) {

        String[] operates = "D G G".split(" ");
        int[] tmp = Arrays.stream("3 3".split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();
        int n = tmp[0];
        int m = tmp[1];

        String[][] matrix = Arrays.stream("F F F\nF F H\nE F E".split("\n"))
                .map(s -> s.split(" "))
                .toArray(String[][]::new);

        System.out.println(getResult(operates, matrix));
    }

    static int[] offset = new int[]{0, -1}; // 蛇头移动初始向左

    public static int getResult(String[] operates, String[][] matrix) {
        int n = matrix.length;
        int m = matrix[0].length;

        LinkedList<Pos> snake = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if ("H".equals(matrix[i][j])) {
                    snake.addLast(new Pos(i, j)); // 找到初始蛇头位置，并使用snake[0]来维护蛇头位置
                }
            }
        }

        for (String operate : operates) {
            switch (operate) {
                case "U":
                    offset[0] = -1;
                    offset[1] = 0;
                    break;
                case "D":
                    offset[0] = 1;
                    offset[1] = 0;
                    break;
                case "L":
                    offset[0] = 0;
                    offset[1] = -1;
                    break;
                case "R":
                    offset[0] = 0;
                    offset[1] = 1;
                    break;
                case "G":
                    Pos head = snake.getFirst();
                    Pos head_next = new Pos(head.x + offset[0], head.y + offset[1]);

                    if (head_next.x < 0 || head_next.x >= n || head_next.y < 0 || head_next.y >= m) {
                        return snake.size();
                    }

                    Pos tail = snake.getLast();

                    switch (matrix[head_next.x][head_next.y]) {
                        case "E":
                            // 如果蛇头去的地方是空地，则:
                            // 蛇身的每个位置都递进为前面一个位置，蛇尾巴位置恢复为空地
                            matrix[tail.x][tail.y] = "E";
                            snake.removeLast();
                            // 蛇头进入新位置
                            matrix[head_next.x][head_next.y] = "H";
                            snake.addFirst(head_next);
                            break;
                        case "F":
                            // 如果蛇头去的地方是食物，则蛇身长度增加一，相当于蛇身各部分位置不变，蛇头变到当前去的位置
                            matrix[head_next.x][head_next.y] = "H";
                            snake.addFirst(head_next);
                            break;
                        case "H":
                            if (head_next.equals(tail)) {
                                // 如果蛇头去的地方是蛇尾，则由于递进关系，蛇头是吃不到蛇尾的
                                snake.addFirst(snake.removeLast());
                            } else {
                                // 如果蛇头去的地方是蛇身，则会吃到自己
                                return snake.size();
                            }
                            break;
                    }

                    break;
            }
        }

        return snake.size();
    }

    // 坐标类
    static class Pos {
        int x;

        int y;

        public Pos(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public boolean equals(Pos pos) {
            return this.x == pos.x && this.y == pos.y;
        }

    }
}